The present invention relates to the display of three-dimensional image data sets, and in particular to raycasting.
Volumetric data sets are usually viewed by being projected unto a two dimensional surface. Two main types of projection systems are used: an orthographic projection, and a perspective projection. In a perspective projection, a single viewpoint is assumed, from which rays emanate and strike the surface. In an orthographic projection, these rays are all perpendicular to a common plane.
Some methods of rendering a volumetric data set onto a two dimensional surface utilize a z-buffer. The values in the z-buffer are equal to the length of rays from the projection point (plane) to the surface. One method of generating the z-buffer, namely raycasting, is applied by following a plurality of rays from their source (point or plane) until they terminate at a solid voxel. Once a z-buffer is generated, the voxels are projected unto the z-buffer and lighting calculations are made, using well known methods, such as described in xe2x80x9cComputer Graphics Principles and Practice, Second Edition in Cxe2x80x9d, by James D. Foley, et al., Addison-Wesly, 1996, the disclosure of which is incorporated herein by reference.
The data set is typically a binary data set, at least for the purposes of raycasting. The value of each voxel is generally assumed to be a discrete sample of a continues spatial function at the center of that voxel. Thus, it is necessary to perform some type of interpolation to determine whether the ray is passing through a transparent voxel or has reached a boundary voxel. Unfortunately, high quality interpolations are generally slow. In addition, some high quality interpolations are not smooth. For example, a long series of values . . . 010101010 . . . will usually not be interpolated as a fixed value 0.5. Generally, some of the waviness of the data will remain after the interpolation, resulting in a wavy interpolation. This is in conflict with the general desire that the z-buffer should not contain frequencies of the order of one over a voxel dimension, because these frequencies are mainly artifacts caused by the limited spatial sampling of the volume.
Cubic interpolations are generally determined using four data points and four constraints. Two sets of constraints, known in the art are:
(1) y(xn)=yn; for n=1 . . . 4, where xn and yn are known and where x is between x2 and x3; and
(2) y(x2)=y2, y(x3)=y3, yxe2x80x2(x2)=(y3xe2x88x92y1)/(x3xe2x88x92x1) and yxe2x80x2(x3)=(y4xe2x88x92y2)/(x4xe2x88x92x2)
It is an object of some embodiments of the present invention to provide a method of ray-casting a voxel data set in which only a required accuracy of values for elements in a z-buffer is achieved. Preferably, the required accuracy is locally determined based on variations in the voxel data set. In one preferred embodiment of the invention, a reduced accuracy of determination of intersections between rays and solid voxels, i.e. the length of the rays, is allowed. Alternatively or additionally, reduced spatial resolution of the z-buffer is allowed, resulting in a less accurate value for the true distance between individual solid voxels and the view origin. Alternatively or additionally, a less accurate interpolation of data is allowed.
It is an object of some embodiments of the present invention, to provide a fast method of cubic interpolation, which is especially suitable for raycasting, but is also useful for other applications, especially those requiring smoothing of data.
It is an object of some preferred embodiments of the present invention, to provide a method of raycasting, in which the spacing of the rays is dependent on a surface variation of the voxel data. In a preferred embodiment of the invention, the method is applied to an image having a plurality of areas having low-contrast features, separated by sharp boundaries. Such images are typical of some types of medical images, where the act of segmentation creates sharp boundaries. Preferably, the spacing of the rays is decreased at the sharp boundaries and increased at the low-detail areas, thereby being adapted to the required accuracy of raycasting.
It is an object of some preferred embodiments of the present invention, to provide a method of raycasting in which the accuracy of determining the length of each ray is dependent on the surface variation.
It is another object of some preferred embodiments of the present invention to provide a method of raycasting, in which the length of a ray is iteratively determined.
It is another object of some preferred embodiments of the present invention to provide a method of raycasting, wherein the type of data interpolation used is adapted to the instant accuracy at which the ray is cast.
It is an object of some preferred embodiments of the invention, to provide a method of cubic interpolation which smoothes out the data, e.g., it smoothes a sequence such as . . . 0101010101010 . . . , without leaving a residual ripple.
In accordance with a preferred embodiment of the present invention, a method of raycasting comprises casting rays in multiple spacing resolutions, starting at a coarse (large) spacing. Rays are added between rays of a previous step, depending on the gradient of data in the z-buffer. If the gradient is small, the z-buffer value is determined by interpolation, rather than by casting a new ray. In a preferred embodiment of the invention, the large spacing casting is applied to a reduced-resolution version of the data set, preferably into a low resolution z-buffer. Preferably, previously cast rays are re-cast, when the resolution of the z-buffer is increased. Preferably, the previously determined z-values are used as a starting point for the search for the solid voxel boundary-ray intersection location, in the finer spacing. Alternatively the raycasting is applied to the fill resolution data set, even in the coarser spacing levels, so that the determined intersection location has a maximal accuracy. Preferably the coarsest spacing level is selected responsive to a statistical property of the data set.
In some preferred embodiments of the invention, externally provided information is used to determine the spacing of the cast rays, at the start of the casting and/or at the end of the casting and/or locally. In one preferred embodiment of the invention, information regarding the clinical interest of a portion of the data is available. Areas which are of more clinical interest are preferably ray cast with a smaller initial inter-ray spacing and/or a lower gradient threshold. In one preferred embodiment of the invention, areas of clinical interest are automatically identified by registering the data set with a previously interpreted data set in which areas of interest are indicated.
In a preferred embodiment of the invention, the inter-ray spacing and/or the gradient threshold and/or other factors which affect the accuracy of the raycasting are dependent on the ray length and/or on the angle between the ray and the voxel surface and/or on the relative location of the ray in the field of view. Preferably, a highest image quality is desired for voxels which are nearer the center of the field of view and within a certain range of distances from the viewing origin. Preferably, this higher image quality is attained by increasing the accuracy of determination of the z-buffer for these voxels. In a preferred embodiment of the invention, a user may enter parameters which define the required accuracy and/or relative image quality for voxels at different distances, angles and/or surface angles.
In accordance with a preferred embodiment of the present invention, additionally or alternatively to coarse ray-spacing, a reduced accuracy of ray length determination is allowed. In a preferred embodiment of the invention, the intersection between the ray and a voxel is searched for, other than by sequentially tracing along the ray. In one preferred embodiment of the invention, a suspected intersection between a ray and a voxel is determined using a reduced resolution data set, i.e., using a different granularity. Thereafter, a higher resolution data set is used to pin-point and/or remove the suspected intersection from consideration. Preferably, the process advances by increasing the resolution and determining, in the increased resolution data set, whether the front of the ray is beyond or in front of a solid voxel. Alternatively or additionally to modifying the resolution of the data set, other methods of modifying the accuracy of the intersection determination may be used, for example, the step size at which the ray is examined for intersections.
In accordance with a preferred embodiment of the invention, the type and/or quality of the interpolation used to determine an intersection between a voxel and a ray, is related to the accuracy at which the intersection is being determined. Higher quality (and slower) interpolations are used when the accuracy is high.
In accordance with a preferred embodiment of the invention, a novel cubic interpolation method is provided. One aspect of an interpolation method, in accordance with some preferred embodiments of the invention, is that it combines smoothing with interpolation. Preferably, the interpolation is determined by a number of constraints and different amounts of smoothing are effected by different constraints. In a preferred embodiment of the invention, at least some of the constraints are not smoothing constraints. Another aspect of an interpolation method, in accordance with some preferred embodiments of the invention, is that the interpolation is not constrained to pass through the points which are used for interpolation.
In accordance with a preferred embodiment of the invention, the interpolation is smoother than standard cubic interpolation. One advantage of a smooth interpolation relates to the method of data packing typically used for voxel data. Typically, more than one voxel is packed into a single machine word. In particular, when a bit volume is used to represent solid voxels, only a single bit is used for each voxel. Most computers have a computational difficulty with handling data which is not stored as a multiple of a byte or word size, especially when the data is stored as fractions of bytes. By performing smoothing as part of interpolation, significant amounts of memory and computations may be saved, especially with regard to unpacking data and storing such data after smoothing in an unpacked data array. It should be appreciated that in some preferred embodiments of the invention, interpolation with smoothing requires the same number of computational steps as does interpolation without smoothing.
In a preferred embodiment of the invention, the original data is never smoothed, so that it can be stored in a more memory efficient manner.
In a preferred embodiment of the invention, a three-dimensional approximation is applied as a plurality of one dimensional approximations. In a first step, a voxel cube of extent 4xc3x974xc3x974 is reduced to an interpolated voxel square of extent 4xc3x974, by 16 parallel one-dimensional interpolations. The square is reduced to a (double interpolated) line of voxels, by 4 one-dimensional interpolations. The line is reduced to a (triple) approximated voxel by a single application of a one-dimensional interpolation. In some preferred embodiments of the invention, fewer or additional voxels may be utilized for the interpolation, in order to affect the quality of the interpolation.
There is therefore provided in accordance with a preferred embodiment of the invention, a method of determining a z-buffer for a voxel data set, comprising:
first raycasting at least a first ray to determine a value for a first z-buffer element; and
second raycasting at least a second ray to determine a value for a second z-buffer element,
wherein said z-buffer element values are determined at different accuracies, which different accuracies are responsive to characteristics of the data set at a neighborhood of said rays.
Preferably, said different accuracies are achieved by modifying the accuracy of determination of an intersection between a cast ray and a solid voxel of said data set.
In a preferred embodiment of the invention, determining an intersection comprises first performing a low accuracy determination and then performing at least one higher accuracy determination of said intersection, responsive to said first determination.
Additionally or alternatively, modifying the accuracy comprises using different interpolation methods to achieve different accuracies. Alternatively or additionally, said intersection is determined by advancing along a ray and modifying the accuracy comprises modifying a step size of said advance. Alternatively or additionally, modifying said accuracy comprises modifying a granularity of said data set for performing said intersection determination. Alternatively or additionally, said accuracy is determined responsive to a distance of said intersection from an origin of the ray. Alternatively or additionally, said accuracy is determined responsive to a length of time for the intersection determination.
In a preferred embodiment of the invention, said at least first ray comprises a first plurality of rays. Alternatively or additionally, said at least second ray comprises a second plurality of rays.
In a preferred embodiment of the invention, said different accuracies are achieved by raycasting into the z-buffer at the vicinity of the first element and of the second element, with different ray densities. Preferably, the method comprises determining a value of a characteristic at a z-buffer element and casting a ray at the z-buffer element only if the value is above a predetermined threshold.
Preferably, said characteristic is a gradient. Alternatively or additionally, said raycasting comprises first casting a first plurality of rays and said second raycasting comprises raycasting a second plurality of rays, and said second plurality of rays increases the density of rays cast into said z-buffer.
Preferably, said second plurality of rays are cast between rays of said first plurality of rays. Alternatively or additionally, the threshold value is dependent on the number of raycastings performed into the z-buffer. Alternatively or additionally, said estimation uses an estimation method which is determined responsive to the number of raycastings performed into the z-buffer.
There is also provided in accordance with a preferred embodiment of the invention a method of determining a z-buffer for a voxel data set, comprising:
determining an intersection between a cast ray and a solid voxel of said data set, at a first accuracy; and
determining said intersection at at least a second, higher accuracy, responsive to said first determination.
Preferably, said determining at a lower resolution comprises advancing along a ray in steps and performing a determination whether a current position is inside or outside a solid voxel. Preferably, the method comprises determining a direction of advancing along a ray towards an intersection responsive to whether a current position along a ray is inside or outside a solid voxel. Alternatively or additionally the method comprises retracing at least a portion of a step along the ray, between said determining at a lower accuracy level and determining at a higher accuracy level.
In a preferred embodiment of the invention, the method comprises decreasing the accuracy of determination responsive to the amount of time spent at an accuracy level. Alternatively or additionally, the accuracy is at least partially determined by a step size of advancing along a cast ray. alternatively or additionally, the accuracy is at least partially determined by a granularity of the voxel data set. Alternatively or additionally, the accuracy is at least partially determined by a quality of interpolation of a voxel value.
There is also provided in accordance with a preferred embodiment of the invention, a method of interpolation comprising:
providing a data set; and
applying a smoothing interpolation to said data set.
Preferably, the data set is a bit volume, in which each voxel is packed so as to be represented by less than a byte. Preferably, each voxel is represented by a single bit. Alternatively or additionally, the voxels are not unpacked for said smoothing interpolation.
In a preferred embodiment of the invention, the interpolation is a cubic interpolation. Alternatively or additionally, said interpolation requires an equal amount of steps as an interpolation which is of the same order but which does not perform smoothing. Alternatively, said smoothing interpolation requires fewer steps than smoothing and applying an interpolation which is of the same order but which does not perform smoothing.
In accordance with a preferred embodiment of the invention, said interpolation uses at least two points which straddle a point to be interpolated and said interpolation is not constrained to pass through at least one of the points which is adjacent said point to be interpolated. Preferably, said interpolation uses four points and wherein said interpolation is not constrained to pass through the two points which are adjacent to said point to be interpolated.
In a preferred embodiment of the invention, the method comprises determining said smoothing interpolation, based on a plurality of constraints. Preferably, said plurality of constraints comprises at least one smoothing constraint. Preferably, said plurality of constraints comprises at least two smoothing constraints. Preferably, said at least two constraints comprise at least one constraint on a value of the interpolation. Alternatively or additionally, said at least two constraints comprise at least one constraint on a derivative of said interpolation.
In a preferred embodiment of the invention, not all of said constraints utilize a same smoothing. Preferably, at least one of said constraints does not induce any smoothing.
In a preferred embodiment of the invention, the method comprises utilizing said smoothed interpolated value to determine an intersection between a cast ray and a solid voxel. Alternatively or additionally, the smoothing interpolation meets the following constraints, where y1, y2, y3 and y4 are values of points in the data set at points x1, x2, x3 and x4, respectively and where x1 less than x2 less than x less than x3 less than x4:             y      ⁡              (                  x          2                )              =                            y          1                +                  2          ⁢                      y            2                          +                  y          3                    4                  y      ⁡              (                  x          3                )              =                            y          2                +                  2          ⁢                      y            3                          +                  y          4                    4      
Alternatively or additionally, the smoothing interpolation meets the following constraints, where y1, y2, y3 and y4 are values of points in the data set at points x1, x2, x3 and x4, respectively and where x1 less than x2 less than x less than x3 less than x4:                     y        xe2x80x2            ⁡              (                  x          2                )              =                            y          3                -                  y          1                                      x          3                -                  x          1                                        y        xe2x80x2            ⁡              (                  x          3                )              =                            y          4                -                  y          2                                      x          4                -                  x          2                    
Alternatively or additionally, said smoothing interpolation generates an interpolated value 0.5 for runs of values . . . 0, 1, 0, 1, 0, 1, 0, 1 . . . , the value 0 for runs of zeros and the value 1 for runs of ones.
Alternatively or additionally, the derivative of the smoothing interpolation is continuous.
There is also provided in accordance with a preferred embodiment of the invention, a method of determining a z-buffer for a voxel data set, comprising:
adding a plurality of additional solid voxels to said data set;
casting at least one ray to the voxel dataset, in the direction of at least one of said additional voxels;
determining an intersection between said ray and a solid voxel of said dataset; and
determining if said solid voxel at said intersection is one of said additional voxels.
Preferably, said additional solid voxels enclose said voxel data set.
In a preferred embodiment of the invention, as described hereinabove, the data set is a medical data set.